package com.lxq.LeetCode.fullJustify;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Solution {
    public static void main(String[] args) {

        String[] words = {"What", "must", "be", "acknowledgment", "shall", "be"};
        List<String> res = fullJustify(words, 16);
        System.out.println(res);
    }

    public static List<String> fullJustify(String[] words, int maxWidth) {
        List<String> res = new ArrayList<>();
        if (words.length == 1) {
            String temp = words[0];
            temp += String.join("", Collections.nCopies(maxWidth - temp.length(), " "));
            res.add(temp);
            return res;
        }
        recursion(0, res, words, maxWidth);

        return res;
    }

    public static void recursion(int pWords, List<String> res, String[] words, int maxWidth) {
        StringBuffer sb = new StringBuffer();
        sb.append(words[pWords++]);
        while (pWords < words.length && (maxWidth - sb.length()) >= words[pWords].length() + 1) {
            sb.append(" ").append(words[pWords]);
            pWords++;
        }
        if (pWords < words.length) {
            int spaceNums = maxWidth - sb.length();
            int index = 0;
            while (spaceNums-- > 0) {
                while (sb.charAt(index) == ' ') {
                    index++;
                }
                index = sb.indexOf(" ", index + 1);
                index = index == -1 ? sb.indexOf(" ", 0) : index;
                if (index == -1) {
                    sb.append(String.join("", Collections.nCopies(spaceNums + 1, " ")));
                    break;
                }
                sb.insert(index, " ");
            }
            res.add(sb.toString());
            recursion(pWords, res, words, maxWidth);
        } else {
            sb.append(String.join("", Collections.nCopies(maxWidth - sb.length(), " ")));
            res.add(sb.toString());
        }

    }

}
